The present invention relates to content addressable memories (CAMs) and particularly to the use of comparand registers within CAMs and/or CAM based systems.
Due to the increased prevalence of information networks, including the Internet, content addressable memories (CAMs) continue to proliferate. CAMs, also referred to as xe2x80x9cassociative memoriesxe2x80x9d can provide rapid matching functions that are often needed in routers and network switches to process network packets. As just one example, a router can use a matching function to match the destination of an incoming packet with a xe2x80x9cforwardingxe2x80x9d table. The forwarding table can provide xe2x80x9cnext hopxe2x80x9d information that can allow the incoming packet to be transmitted to its final destination, or to another node on the way to its final destination. Of course, CAMs can also be used for applications other than network hardware.
A CAM may perform the matching functions described above by providing the ability to apply a search key or xe2x80x9ccomparandxe2x80x9d to a table of stored data values. A CAM may then determine if any of the data values match a given search key. A typical conventional search operation, along with a general architecture of a conventional CAM system will now be described in more detail.
Referring to FIG. 9A, an example of a conventional CAM system is shown, and is designated by the general reference number 900. A conventional CAM system 900 may include a network processing unit (NPU) 902, and a number of CAM blocks 904-1 and 904-2 that may be connected by control and data signals 908.
Referring now to FIG. 9B, CAM blocks 904 are shown in more detail, and may include a CAM array 912, CAM control circuits 914, and a comparand register (CMPR) set 916.
A CAM array 912 may contain any number of CAM storage cells. Data may be written to and/or read from such CAM storage cells. A CAM array 912 may also support a search function, where a search key or xe2x80x9ccomparandxe2x80x9d may be compared against data stored in any number of CAM storage cells. If the data in any CAM storage cell matches a comparand value, then a search hit may be indicated. Otherwise, a search miss may be indicated.
CAM control circuits 914 can take CAM control and data signalsl 908 as inputs and generate signals that may be necessary to control the operation of a CAM array 912.
A CMPR set 916 may include any number of storage locations that may be used to store comparand values used for search operations. In the particular example of FIG. 9B, a CMPR set 916 includes eight storage locations. Comparand values may be loaded into a location of a CMPR set 916 by CAM control and data signals 908.
Having described an example of a CAM based system, as well as a CAM block, a conventional CAM search operation will now be described. To perform la search operation, an NPU 902 may provide to CAM blocks 904 a comparand value as well as the location within a comparand register set 916 to store the comparand data. A comparand value may then be compared to all the CAM storage locations within a CAM array 912.
If any of the values stored in a CAM array 912 matches the comparand value, it is considered a search xe2x80x9chit.xe2x80x9d Various actions may be taken in response to a search hit. As an example, an index value may be generated for the CAM storage location that matches a comparand value. Further, a search result may be communicated back to an NPU 902 by way of control and data signals 908. It is noted that in a conventional case, a comparand register set 916 location corresponding to a matching comparand value may then be free for use again in a system.
If none of the values stored in a CAM array 912 matches a comparand value, such an operation may be considered a search xe2x80x9cmissxe2x80x9d. In this case, a comparand value stored at the specified comparand register set 916 location may be retained for later use. In particular, such a comparand value may be used in a xe2x80x9clearnxe2x80x9d operation. A learn operation provides a way for the CAM to xe2x80x9clearnxe2x80x9d the comparand value for a previously missed search operation. Thus, the next time the same comparand value is applied, a search hit may result.
A conventional CAM learn operation will now be described in more detail. To perform a learn operation, an NPU 902 may provide to CAM blocks 904 a location within a comparand register set 916 that contains the comparand value to be xe2x80x9clearnedxe2x80x9d. The comparand value stored at this location can then be written into a CAM array 912 at a free or otherwise designated storage location. In this way, the CAM has xe2x80x9clearnedxe2x80x9d the comparand value from a missed search. Associated data for such a comparand value may be written to, or otherwise made available, at some location indexed by a given designated location.
In a conventional learn operation, such as that described above, a network processing unit (NPU) and/or system software or firmware controlling such operations, may have to keep track of the values stored in the comparand register set 916. For example, to perform a learn operation, a system may keep track of which comparand register set 916 locations contain comparand values for a missed search operations. Thus, in performing a learn operation, an NPU 902 may initially issue a search based on a register within a register set 916. When the search indicates a xe2x80x9cmiss,xe2x80x9d an NPU 902 recalls the register used in an initial search, and orders a learn operation based upon the same register.
Thus, a conventional approach may require an NPU 902 to access a CAM block (904-1 and 904-2) at least twice in an overall learn operation. One access issues an initial search operation. A second access issues a corresponding learn operation when the initial search gives a miss result. Further, an NPU 902 may have to track which register stores a comparand value within a given CAM block (904-1 and 904-2).
Because reductions in the number of times devices may access one another can increase the speed and efficiency of a system, it would be desirable to arrive at some way of reducing accesses between an NPU and a CAM blocks, or the like.
It is also noted that conventional approaches may result in constraints on when a learn operation may be performed. In particular, if all locations of a CMPR set 916 store comparand values that are in use, it may not be possible to issue a learn command.
Thus, it would be desirable to arrive at some way of providing more flexibility in how comparand storage registers are utilized in CAM system.
According to the present invention, a content addressable memory (CAM) system may include a free index list and a busy index list. A free index list may include locations for storing index values that correspond to comparand values for use in search operations. A busy index list may include locations for storing index values that correspond to comparand values for use in non-search operations.
According to one aspect of the embodiments, a free index list may include registers that store indexes to comparand registers.
According to another aspect of the embodiments, a busy index list may also include registers that store indexes to the comparand registers.
According to another aspect of the embodiments, a CAM system may further include head and tail pointers for a free index list that indicates the start and end of valid entries in the free index list. Head and tail pointers may also be provided for a busy index list.
According to another aspect of the embodiments, a CAM system may further include a descriptor command list. A descriptor command list may store values associated with commands issued to CAM cells. Each location of a descriptor command list may include an index field that stores an index value for a comparand, as well as a valid field that stores a valid indication for the descriptor command list location.
According to another aspect of the embodiments, a CAM system may further include at least one CAM block. A CAM block may include at least one array of CAM cells and comparand registers for storing comparand values. Index values may correspond to comparand register locations.
The present invention may also include various methods for monitoring comparand index values. Such methods may be associated with particular content addressable memory (CAM) operations, such as a restart operation, search operation, free index operation, and learn operation.
According to one aspect of the embodiments, a method may include assigning a comparand index value to a free comparand list. A comparand corresponding to the comparand index value may then be compared with a plurality of CAM locations. If the comparand matches a CAM location, the comparand index value may be removed from a free comparand list. If the comparand does not match a CAM location, the comparand index value may be assigned to a busy comparand list.
According to another aspect of the embodiments, each search command may be associated with a descriptor. Prior to comparing the comparand to CAM locations, a valid indication may be set to a valid state within the descriptor associated with the search command.
According to another aspect of the embodiments, after removing a comparand index value, a valid indication may be set to an invalid state within a descriptor associated with a search command.
According to the present invention, a method according to the present invention may alternately include initializing a list for free comparand index values and a list for busy comparand index values. Such a method may also include initializing pointers to the lists for free and busy comparand index values.
According to one aspect of the embodiments, initializing the pointers may include initializing head and tail pointers that indicate the start and end of the free comparand index list, respectively, and/or busy comparand index list, respectively.
According to another aspect of the embodiments, a method may further include freeing up at least one busy comparand index value when there are no more free comparand index values.
According to another aspect of the embodiments, when at least one busy comparand index value is made free in response to no more free comparand index values, a descriptor command associated with the comparand index value may be set to an invalid state.
According to the present invention, a method according to the present invention may alternately include executing a learn operation with a comparand value identified by a comparand index value. The comparand index value may be stored in a busy comparand index list. The comparand index value may then be moved from the busy comparand index list to a free comparand index list.
According to one aspect of the embodiments, the learn operation may be executed according to a descriptor. If the descriptor is valid, a learn operation may be executed and a comparand index value moved from a busy list to a free list, as noted above. In addition, the descriptor may be changed from a valid indication to an invalid indication.
According to one aspect of the embodiments, the learn operation may be executed according to a descriptor. If the descriptor is not valid, a search operation may be performed with a comparand value. A comparand index value associated with the comparand value may then be assigned to the busy comparand list. A learn operation may then be executed and a comparand index value moved from a busy list to a free list, as noted above.